应用场景
大数据 ， 快速查找 ， 不介意小概率误判
- 分布式磁盘 IO
- 爬虫
- 黑名单过滤
优缺点
优点
- 空间小，相比
list,RB-tree,hash不用存数据 - 查询快，\(O(k)\)级别的查询效率，还能并行
缺点
- 有时候同学不在寝室，他却告诉我们在；但是他们告诉我们不在，就一定不在
- 删除难
原理
布隆过滤器的原理是，当一个元素被加入集合时，通过 \(K\) 个散列函数将这个元素映射成一个位数组中的 \(K\) 个点，把它们置为 1。检索时，我们只要看看这些点是不是都是 1 就（大约）知道集合中有没有它了：如果这些点有任何一个 0，则被检元素一定不在；如果都是 1，则被检元素很可能在。这就是布隆过滤器的基本思想。
一般了解到这里就可以。如果你还想看，下面就是无聊的公式推导了。 参考 wiki 吧
搞事情
搞哈希算法
哈希算法 = 数组 + 哈希函数
碰撞了怎么办？
两种办法：开链法和闭散列法。开链法就是将映射到同一下标的所有元素形成一个链表，挂到该位置下面；闭散列法就是将冲突的元素按照某种方式向后排放。
缺点
- 开链法：极端条件下又变成 \(O(n)\) 了
- 闭散列法：多吃多占，影响了下个本来映射到该位置的元素
负载因子
就是当前哈希表中存放的元素数和数组长度的比值。一般来说，负载因子超过 0.8，就需要对哈希表扩容。即重新构造一个更大的数组，将所有元素转移过去，再释放原有空间。
误判概率
\[P \approx\left(1-e^{-\frac{n k}{m}}\right)^{k} \]
看看影响因素
- 集合中元素数量 \(n\)
- 数组大小 \(m\)
- 选取的 \(k\) 个哈希函数
从这个公式也可以看出，\(m\)和 \(n\) 成比例才可以保证误报率不变。\(k\) 不用管他。
参考：
- https://www.wikiwand.com/en/Bloom_filter
- https://smartbrave.github.io/posts/3e0efa6d